package com.leetcode.p100;

import com.bean.TreeNode;
import com.utils.DataUtils;
import com.utils.TreeUtils;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Test113 {

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<Integer> stack = new Stack<>();
        bfs(res, stack, root, 0, targetSum);
        return res;
    }

    private void bfs(List<List<Integer>> res, Stack<Integer> stack, TreeNode lisNode, int sum, int targetSum) {
        if (lisNode.left == null && lisNode.right == null) {
            stack.push(lisNode.val);
            sum += lisNode.val;
            if (sum == targetSum) {
                res.add(new ArrayList<>(stack));
            }
            return;
        }

        sum += lisNode.val;
        stack.push(lisNode.val);

        if (lisNode.left != null) {
            bfs(res, stack, lisNode.left, sum, targetSum);
            stack.pop();
        }

        if (lisNode.right != null) {
            bfs(res, stack, lisNode.right, sum, targetSum);
            stack.pop();
        }
    }

    public static void main(String[] args) {
        TreeNode treeNode = TreeUtils.buildTree("5,4,8,11,null,13,4,7,2,null,null,5,1");
        TreeUtils.showTree(treeNode);
//        Test113 test = new Test113();
//        DataUtils.printListListInteger(test.pathSum(treeNode, 22));
    }
}
